1. Field of the Invention
The present invention relates to a variable length code decoding apparatus and method suitable for parallel decoding of a variable length code.
2. Description of the Related Art
In a conventional variable length code parallel decoding apparatus, when a variable length code is parallelly decoded, data to be decoded is parallelly extracted from a code bit string forming the variable length code into a register, and is input to an address circuit, as disclosed in U.S. Pat. No. 3,883,847. A first table (decoding result data table) is accessed using the data input to the address circuit as an address (entry address). Data associated with a decoding result (decoding result data) is set at each entry of this table. The start position of a code to be decoded (the decoding start bit position in a code bit string) can be detected on the basis of a "code length" included in the decoding result data.
In the known variable length code decoding apparatus, since codes which frequently appear normally have a small code length (smaller than a length of data input to the address circuit), they can be decoded within one cycle. In contrast to this, since codes which do not frequently appear normally have a large code length (exceeding a length of data input to the address circuit), they are decoded in two cycles. For example, for codes encoded by an MH (Modified Huffman) method, an MR (Modified READ) method, or an MMR (Modified MR) method, if data input to the address circuit is assumed to have an 8-bit length, two-dimensional codes and one-dimensional codes having a code length of 8 bits or less can be decoded within one cycle. However, one-dimensional codes having a code length of 9 bits or more require two or more cycles for decoding. A maximum code length of a one-dimensional code is 9 bits for a white code (white run code), and 13 bits for a black code (black run code).
When decoding is performed in two cycles in the known variable length code decoding apparatus, the length of a portion to be decoded in the first cycle of the total code length is fixed (e.g., 8 bits), and the remaining portion is decoded in the second cycle. In the decoding apparatus, a plurality of second tables are prepared for decoding in the second cycle, and one of the second tables is designated on the basis of predetermined data in entry data of the first table obtained in the first cycle, i.e., decoding result data indicating a partial (fixed length) decoding result (intermediate decoding result). Since the predetermined data corresponds to a state of the partial decoding result, it can be regarded as a kind of status data.
In the conventional variable length code decoding apparatus disclosed in U.S. Pat. No. 3,883,847, when parallel decoding of a variable length code is performed in two cycles, in, e.g., an 8-bit machine, 8 bits from the start bit of an objective code are partially decoded in the first cycle, and the remaining bits are decoded in the second cycle using status data indicating the partial decoding result. For this reason, when the prior art is applied to an 8-bit/cycle variable length code decoding apparatus which processes MH-, MR-, or MMR-encoded codes described in the CCITT (Comite Consultatif International Telegraphique et Telephonique) recommendations T.4 and T.6, for example, when a one-dimensional code of binary image data is to be decoded, status data indicating the partially decoded result in the first cycle (used for decoding in the second cycle) requires 10 states for a white code (indicated by white B through white K in FIGS. 1A through 3) and status data for 8 states for a black code (indicated by black B through black I in FIGS. 1A through 3), as can be seen from code tables shown in FIGS. 1A through 3. In the prior art, since the number of types of states to be transferred from the first cycle to the second cycle is very large, the size of the decoding result data becomes large, resulting in an increase in the number of decoding result data tables.